695. Max Area of Island

Problem Statement

You are given an m x n binary matrix grid. An island is a group of 1's (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.

The area of an island is the number of cells with a value 1 in the island.

Return the maximum area of an island in grid. If there is no island, return 0.

Example 1:

Input: grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]
Output: 6
Explanation: The answer is not 11, because the island must be connected 4-directionally.

Example 2:

Input: grid = [[0,0,0,0,0,0,0,0]]
Output: 0

Constraints:

m == grid.length
n == grid[i].length
1 <= m, n <= 50
grid[i][j] is either 0 or 1.

Solution:

Rust

impl Solution {
    pub fn max_area_of_island(grid: Vec<Vec<i32>>) -> i32 {
        let mut grid = grid;
        let (rows, cols) = (grid.len(), grid[0].len());

        let mut max_area = 0;

        for row in 0..rows {
            for col in 0..cols {
                max_area = max_area.max(Self::dfs(&mut grid, row, col))
            }
        }

        max_area
    }

    fn dfs(grid: &mut Vec<Vec<i32>>, row: usize, col: usize) -> i32 {
        let (rows, cols) = (grid.len(), grid[0].len());
        if row >= rows || col >= cols || grid[row][col] == 0 {
            return 0;
        }

        grid[row][col] = 0;

        1 + Self::dfs(grid, row + 1, col)
            + Self::dfs(grid, row, col + 1)
            + Self::dfs(grid, row - 1, col)
            + Self::dfs(grid, row, col - 1)
    }
}

695. Max Area of Island #

Problem Statement #

Solution: #

... #

695. Max Area of Island

Problem Statement

Solution:

...